import { measureSort, swap, testSort } from "hy-algokit";

function quickSort(arr: number[]): number[] {
  partition(0, arr.length - 1);
  function partition(left: number, right: number): void {
    if (left >= right) return;

    /*    将基准元素移动到中间
 const mid = left + Math.floor((left + right) / 2);
    if (arr[left] > arr[right]) swap(arr, left, right);
    if (arr[mid] > arr[right]) swap(arr, mid, right);
    if (arr[left] > arr[mid]) swap(arr, left, mid);
    swap(arr, mid, right);
    const pivot = arr[right];
    let i = left + 1;
    let j = left - 1; */

    let pivot = arr[right];

    let i = left;
    let j = right - 1;

    while (i <= j) {
      while (arr[i] < pivot) {
        i++;
      }
      while (arr[j] > pivot) {
        j--;
      }
      if (i <= j) {
        swap(arr, i, j);
        i++;
        j--;
      }
    }
    swap(arr, i, right);
    partition(left, j);
    partition(i + 1, right);
  }

  return arr;
}

testSort(quickSort);

measureSort(quickSort);
